package 排序;

import java.util.Arrays;

/**
 * 把最大元素和当前堆中数组的最后一个元素交换位置，并且不删除它，
 * 那么就可以得到一个从尾到头的递减序列，从正向来看就是一个递增序列，
 * 这就是堆排序。
 */
public class 堆排序 {

    public static void heapSort(int[] a) {
        int N = a.length - 1;
        // 从右至左进行下沉操作
        for (int k = N / 2; k >= 1; k--) {
            sink(a, k, N);
        }
        while (N > 1) {
            swap(a, 1, N--);
            sink(a, 1, N);
        }
    }
    // 下沉
    private static void sink(int[] a, int k, int N) {
        while (2 * k <= N) {
            int j = 2 * k;
            if (j < N && less(a[j], a[j + 1]))
                j++;
            if (!less(a[k], a[j]))
                break;
            swap(a, k, j);
            k = j;
        }
    }

    private static boolean less(Comparable v, Comparable w) {
        // 若 v 小于 w 则返回负数
        return v.compareTo(w) < 0;
    }

    private static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    public static void main(String[] args) {
        int[] a = {1, 9, 2, 8, 3, 6, 7};
        System.out.println(Arrays.toString(a));
        heapSort(a);
        System.out.println(Arrays.toString(a));
    }

}
